/*
*These codes for tree with two children is developed by XioaDe li in July fifteenth in 2016.
*Please read "readme.md" before you use these codes.
*Thank for your using.
*
*/
#pragma once
#ifndef TREE
#define TREE
#include<vector>
#include<queue>
#include<string.h>
struct node
{
	bool have_value;	//if have value
	int content;  		//content is value
	node *left;
	node *right;
	node() :have_value(false), left(NULL), right(NULL){}

};
node* newnode()
{
	return new node();
}
bool addnode(node* root, int v, char* s)
{
	int n = strlen(s);
	node* u = root;
	for (int i = 0; i<n; i++)
	{
		if (s[i] == 'L')
		{
			if (u->left == NULL)
				u->left = newnode();
			u = u->left;
		}
		else
		{
			if (s[i] == 'R')
			{
				if (u->right == NULL)
					u->right = newnode();
				u = u->right;
			}
		}
	}
	if (u->have_value )
		return false;
	u->content = v;
	u->have_value = true;
	return true;
}
bool bfs(std::vector<int>& ans, node* root)
{
	std::queue<node*> q;
	ans.clear();
	q.push(root);
	while (!q.empty())
	{
		node* u = q.front();
		q.pop();
		if (!u->have_value)
			return false;
		ans.push_back(u->content);
		if (u->left != NULL)
			q.push(u->left);
		if (u->right != NULL)
			q.push(u->right);
	}
	return true;
}
bool XXBLintree(node* root, std::vector<int>& ans)
{
	ans.push_back(root->content);
	if (root->left != NULL)
		XXBLintree(root->left, ans);
	if (root->right != NULL)
		XXBLintree(root->right, ans);
	return true;
}
bool ZXBLintree(node* root, std::vector<int>& ans)
{
	if (root->left != NULL)
		ZXBLintree(root->left, ans);
	ans.push_back(root->content);
	if (root->right != NULL)
		ZXBLintree(root->right, ans);
	return true;
}
bool HXBLintree(node* root, std::vector<int>& ans)
{
	if (root->left != NULL)
		HXBLintree(root->left, ans);
	if (root->right != NULL)
		HXBLintree(root->right, ans);
	ans.push_back(root->content);
	return true;
}
void removetree(node *root)
{
	if (root == NULL)
		return;
	removetree(root->left);
	removetree(root->right);
	delete root;
}

class tree
{
public:
	node* root;
	std::vector<node*> pool;
	tree()
	{
		root = newnode();
		pool.push_back(root);
	}
	tree(int i)
	{
		root = newnode();
		root->content = i;
		root->have_value = true;
		pool.push_back(root);
	}
	~tree()
	{
		for (int i = 0; i<(int)pool.size(); i++)
			delete pool[i];
	}
	bool addnode(node* r, int v, char* s)
	{
		int n = strlen(s);
		node* u = r;
		for (int i = 0; i<n; i++)
		{
			if (s[i] == 'L')
			{
				if (u->left == NULL)
					u->left = newnode();
				u = u->left;
				pool.push_back(u);
			}
			else
			{
				if (s[i] == 'R')
				{
					if (u->right == NULL)
						u->right = newnode();
					u = u->right;
					pool.push_back(u);
				}
			}
		}
		if (u->have_value)
			return false;
		u->content = v;
		u->have_value = true;
		return true;
	}
};
#endif
